{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Visit Array Positions to Maximize Score"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxScore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #访问数组中的位置使分数最大"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;和一个正整数&nbsp;<code>x</code>&nbsp;。</p>\n",
    "\n",
    "<p>你 <strong>一开始</strong>&nbsp;在数组的位置 <code>0</code>&nbsp;处，你可以按照下述规则访问数组中的其他位置：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果你当前在位置&nbsp;<code>i</code>&nbsp;，那么你可以移动到满足&nbsp;<code>i &lt; j</code>&nbsp;的&nbsp;<strong>任意</strong>&nbsp;位置&nbsp;<code>j</code>&nbsp;。</li>\n",
    "\t<li>对于你访问的位置 <code>i</code>&nbsp;，你可以获得分数&nbsp;<code>nums[i]</code>&nbsp;。</li>\n",
    "\t<li>如果你从位置 <code>i</code>&nbsp;移动到位置 <code>j</code>&nbsp;且&nbsp;<code>nums[i]</code> 和&nbsp;<code>nums[j]</code>&nbsp;的 <strong>奇偶性</strong>&nbsp;不同，那么你将失去分数&nbsp;<code>x</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回你能得到的 <strong>最大</strong>&nbsp;得分之和。</p>\n",
    "\n",
    "<p><strong>注意</strong>&nbsp;，你一开始的分数为&nbsp;<code>nums[0]</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [2,3,6,1,9,2], x = 5\n",
    "<b>输出：</b>13\n",
    "<b>解释：</b>我们可以按顺序访问数组中的位置：0 -&gt; 2 -&gt; 3 -&gt; 4 。\n",
    "对应位置的值为 2 ，6 ，1 和 9 。因为 6 和 1 的奇偶性不同，所以下标从 2 -&gt; 3 让你失去 x = 5 分。\n",
    "总得分为：2 + 6 + 1 + 9 - 5 = 13 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [2,4,6,8], x = 3\n",
    "<b>输出：</b>20\n",
    "<b>解释：</b>数组中的所有元素奇偶性都一样，所以我们可以将每个元素都访问一次，而且不会失去任何分数。\n",
    "总得分为：2 + 4 + 6 + 8 = 20 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i], x &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [visit-array-positions-to-maximize-score](https://leetcode.cn/problems/visit-array-positions-to-maximize-score/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [visit-array-positions-to-maximize-score](https://leetcode.cn/problems/visit-array-positions-to-maximize-score/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,6,1,9,2]\\n5', '[2,4,6,8]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        m,n=nums[0],nums[0]#m i处为奇数，\n",
    "        if nums[0]%2==1:\n",
    "            n-=x\n",
    "        else:\n",
    "            m-=x\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]%2==1:\n",
    "                m=max(m,n-x)+nums[i]\n",
    "            else:\n",
    "                n=max(n,m-x)+nums[i]\n",
    "        return max(m,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        #两个限制，一个是只能向右走，一个是值不同的话减去x\n",
    "        \"\"\"\n",
    "        一个位置可以由奇最大也可以由偶最大转来，\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        dp = [[0]*2 for _ in range(n)]\n",
    "        if nums[0] % 2 == 0:\n",
    "            dp[0][0] = nums[0]\n",
    "            dp[0][1] = nums[0]-x\n",
    "        else:\n",
    "            dp[0][1] = nums[0]\n",
    "            dp[0][0] = nums[0] - x\n",
    "        for i in range(1, n):\n",
    "            if nums[i] % 2 == 0:\n",
    "                dp[i][0] = max(dp[i-1][0] + nums[i],dp[i-1][1] + nums[i] - x)\n",
    "                dp[i][1] = dp[i-1][1]\n",
    "            else:\n",
    "                dp[i][1] = max(dp[i-1][1] + nums[i],dp[i-1][0] + nums[i] - x)\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "        return max(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        n=len(nums)\n",
    "        last=nums[0]\n",
    "        dp=[[0,0] for _ in range(n)]\n",
    "        if nums[0]%2==0:\n",
    "            dp[0][0]=nums[0]\n",
    "            dp[0][1]=nums[0]-x\n",
    "        else:\n",
    "            dp[0][0]=nums[0]-x\n",
    "            dp[0][1]=nums[0]\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if nums[i]%2==0:\n",
    "                dp[i][0]=max(dp[i-1][0]+nums[i],dp[i-1][1]+nums[i]-x)\n",
    "                dp[i][1]=dp[i-1][1]\n",
    "            else:\n",
    "                dp[i][1]=max(dp[i-1][1]+nums[i],dp[i-1][0]+nums[i]-x)\n",
    "                dp[i][0]=dp[i-1][0]   \n",
    "        print(dp) \n",
    "        return max(dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[[0 for _ in range(2)]for _ in range(n)]\n",
    "        dp[0][nums[0]%2]=nums[0]\n",
    "        dp[0][(nums[0]+1)%2]=-float(\"inf\")\n",
    "        for i in range(1,n):\n",
    "            if nums[i]%2==0:\n",
    "                dp[i][0]=max(dp[i-1][0]+nums[i],dp[i-1][1]+nums[i]-x)\n",
    "                dp[i][1]=dp[i-1][1]\n",
    "            else:\n",
    "                dp[i][1]=max(dp[i-1][1]+nums[i],dp[i-1][0]+nums[i]-x)\n",
    "                dp[i][0]=dp[i-1][0]\n",
    "        print(dp)\n",
    "        return max(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        N = len(nums)\n",
    "        process = []\n",
    "        i = 0\n",
    "        while i < N:\n",
    "            j, cur = i + 1, nums[i]\n",
    "            while j < N and (nums[j] - nums[i]) & 1 == 0:\n",
    "                cur += nums[j]\n",
    "                j += 1\n",
    "            process.append(cur)\n",
    "            i = j\n",
    "\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dfs(i):\n",
    "            if i == 0:\n",
    "                return process[0]\n",
    "            elif i == 1:\n",
    "                return process[i] + dfs(i - 1) - x\n",
    "            else:\n",
    "                return process[i] + max(dfs(i - 1) - x, dfs(i - 2))\n",
    "\n",
    "        return max(dfs(i) for i in range(len(process)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        p, last = [], 0\n",
    "        s = 0\n",
    "        for num in nums:\n",
    "            if (num + last) & 1 == 1:\n",
    "                if last > 0:\n",
    "                    p.append(s)\n",
    "                s = 0\n",
    "            s += num\n",
    "            last = num\n",
    "        else:\n",
    "            p.append(s)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == len(p): return 0\n",
    "            if i + 1 == len(p): return dfs(i + 1) + p[i]\n",
    "           \n",
    "            return max(dfs(i + 1) + p[i] - x, dfs(i + 2) + p[i])\n",
    "        \n",
    "        return dfs(0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "       list = []\n",
    "       def getList() -> None:\n",
    "          i = 0\n",
    "          j = 0\n",
    "          n = len(nums)\n",
    "          while j < n:\n",
    "             sum = 0\n",
    "             while j < n and nums[j] % 2 == nums[i] % 2:\n",
    "                sum += nums[j]\n",
    "                j += 1\n",
    "             list.append(sum)\n",
    "             i = j\n",
    "       \n",
    "       @cache\n",
    "       def dfs(i: int) -> int:\n",
    "          if i >= n:\n",
    "             return 0\n",
    "          return max(dfs(i + 1) - x, dfs(i + 2)) + list[i]\n",
    "       getList()\n",
    "       n = len(list)\n",
    "       return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[-1] * 2 for _ in range(n + 1)]\n",
    "        def dfs(i: int, p: int) -> int:\n",
    "            if i == n:\n",
    "                return 0\n",
    "            if dp[i][p] != -1:\n",
    "                return dp[i][p]\n",
    "            v = nums[i]\n",
    "            res = dfs(i + 1, v % 2) + nums[i]\n",
    "            if v % 2 != p:\n",
    "                res -= x\n",
    "            res = max(res, dfs(i + 1, p))\n",
    "            dp[i][p] = res\n",
    "            return res\n",
    "        return dfs(1, nums[0] % 2) + nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        used = [True, True]\n",
    "        def maxS(right,x):\n",
    "            if right == 0:\n",
    "                if nums[right]%2 == 0:\n",
    "                    return -inf,nums[right]\n",
    "                return nums[right],-inf\n",
    "            resodd,reseven = maxS(right-1, x)\n",
    "            # print(resodd,reseven)\n",
    "            \n",
    "            if nums[right]%2 == 0:\n",
    "                \n",
    "                return resodd, max(reseven, reseven+nums[right], resodd+nums[right] - x)\n",
    "            else:\n",
    "                return max(resodd, resodd+nums[right], reseven+nums[right] - x), reseven\n",
    "        return max(maxS(len(nums)-1, x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "\n",
    "        a=[]\n",
    "        c=nums[0]%2\n",
    "        j=0\n",
    "        for v in nums:\n",
    "            cc=v%2\n",
    "            if cc==c:\n",
    "                j+=v\n",
    "            else:\n",
    "                a.append(j)\n",
    "                j=v\n",
    "                c=cc\n",
    "        a.append(j)\n",
    "\n",
    "        x2=x*2\n",
    "\n",
    "        l=len(a)\n",
    "\n",
    "        @cache\n",
    "        def z(i,c):\n",
    "            if i==l:\n",
    "                return 0\n",
    "\n",
    "\n",
    "            nn=a[i]\n",
    "            cc=i%2\n",
    "\n",
    "            if cc==c:\n",
    "                return z(i+1,c)+nn\n",
    "\n",
    "            # if nn<=x:\n",
    "            #     return z(i+1,c)\n",
    "\n",
    "\n",
    "            if nn>=x2:\n",
    "                return z(i+1,cc) +nn-x\n",
    "\n",
    "            res1=z(i+1,c)\n",
    "            res2=z(i+1,cc)+nn-x\n",
    "\n",
    "            return max(res1,res2)\n",
    "\n",
    "\n",
    "        return z(1,0)+a[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        t = [[-1, -1] for _ in range(n)]\n",
    "        d = {0: -1, 1: -1}\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            t[i][0] = d[0]\n",
    "            t[i][1] = d[1]\n",
    "            d[nums[i] % 2] = i\n",
    "\n",
    "        @cache\n",
    "        def dp(i: int) -> int:\n",
    "            if i == n - 1:\n",
    "                return nums[i]\n",
    "            ans = nums[i]\n",
    "            if nums[i] & 1:\n",
    "                if t[i][1] != -1:\n",
    "                    ans = max(ans, nums[i] + dp(t[i][1]))\n",
    "                if t[i][0] != -1:\n",
    "                    ans = max(ans, nums[i] + dp(t[i][0]) - x)\n",
    "            else:\n",
    "                if t[i][0] != -1:\n",
    "                    ans = max(ans, nums[i] + dp(t[i][0]))\n",
    "                if t[i][1] != -1:\n",
    "                    ans = max(ans, nums[i] + dp(t[i][1]) - x)\n",
    "            return ans\n",
    "\n",
    "        return dp(0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        @lru_cache \n",
    "        def dp(i, preIsO):\n",
    "            if i >= n: return 0\n",
    "\n",
    "            curIsO = nums[i] % 2 == 0\n",
    "            if i == 0:\n",
    "                return dp(i + 1, preIsO) + nums[i]\n",
    "            return max(\n",
    "                dp(i + 1, preIsO),\n",
    "                dp(i + 1, curIsO) + nums[i] + (0 if curIsO == preIsO else -x)\n",
    "            )\n",
    "        return dp(0, nums[0] % 2 == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        odd = []\n",
    "        even = []\n",
    "        for idx,v in enumerate(nums):\n",
    "            if v%2:\n",
    "                odd.append(idx)\n",
    "            else:\n",
    "                even.append(idx)\n",
    "        odd.append(n)\n",
    "        even.append(n)\n",
    "        odd = odd[::-1]\n",
    "        even = even[::-1]\n",
    "        \n",
    "        nex_odd = []\n",
    "        nex_even = []\n",
    "        for idx in range(n):\n",
    "            while odd[-1]<=idx:\n",
    "                odd.pop()\n",
    "            nex_odd.append(odd[-1])\n",
    "            while even[-1]<=idx:\n",
    "                even.pop()\n",
    "            nex_even.append(even[-1])\n",
    "        # print(nex_even)\n",
    "        # print(nex_odd)\n",
    "        \n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i>=n:\n",
    "                return 0\n",
    "            res = [nums[i]]\n",
    "            if nums[i]%2:\n",
    "                res.append(nums[i]+f(nex_odd[i]))\n",
    "                res.append(nums[i]+f(nex_even[i])-x)\n",
    "                # print(i,res)\n",
    "            else:\n",
    "                res.append(nums[i]+f(nex_odd[i])-x)\n",
    "                res.append(nums[i]+f(nex_even[i]))\n",
    "                # print(i,res,nex_odd[i],nex_even[i])\n",
    "            return max(res)\n",
    "        # for i in range(n):\n",
    "        #     print(f(i))\n",
    "        return f(0)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            if nums[i] & 1 == j:\n",
    "                res = nums[i] + dfs(i + 1, j)\n",
    "            else:\n",
    "                res = max(dfs(i + 1, j), nums[i] - x + dfs(i + 1, 1 ^ j))\n",
    "            return res\n",
    "\n",
    "        res = nums[0] + dfs(1, nums[0] & 1)\n",
    "        dfs.cache_clear()\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(index: int, oddEven: int, preSelect: bool) -> int:\n",
    "            if index >= n:\n",
    "                return 0\n",
    "\n",
    "            cur = nums[index]\n",
    "            # 不选\n",
    "            cand2 = dfs(index + 1, oddEven, False)\n",
    "            # 选\n",
    "            cand1 = dfs(index + 1, cur & 1, True) + (cur if ((cur & 1) == oddEven) else cur - x)\n",
    "\n",
    "            return cand1 if cand1 > cand2 else cand2\n",
    "\n",
    "        n = len(nums)\n",
    "        res = dfs(1, nums[0] & 1, True) + nums[0]\n",
    "        dfs.cache_clear()\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i==len(nums):\n",
    "                return 0\n",
    "            if i==len(nums)-1:\n",
    "                return nums[i]\n",
    "            if (nums[i]+nums[i+1])%2==0:\n",
    "                return nums[i]+dfs(i+1)\n",
    "            else:\n",
    "                temp=i+1\n",
    "                while temp<len(nums) and (nums[i]+nums[temp])%2!=0:\n",
    "                    temp+=1\n",
    "                return nums[i]+max(dfs(i+1)-x,dfs(temp))\n",
    "        return dfs(0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        @cache\n",
    "        def dp(i):\n",
    "            if i==len(nums)-1:\n",
    "                return nums[i]\n",
    "            if i==len(nums):\n",
    "                return 0\n",
    "            if (nums[i]+nums[i+1])%2==0:\n",
    "                return nums[i]+dp(i+1)\n",
    "            else:\n",
    "                temp=i+2\n",
    "                while temp<len(nums) and (nums[temp]+nums[i])%2!=0:\n",
    "                    temp+=1\n",
    "                return nums[i]+max(dp(i+1)-x,dp(temp))\n",
    "        return dp(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        def sub(i, j):\n",
    "            return x*(int(nums[i]%2 != nums[j]%2))\n",
    "        \n",
    "        @cache\n",
    "        def score(i):\n",
    "            ans = nums[i]\n",
    "            for j in range(i+1, n):\n",
    "                if sub(i, j) == 0:\n",
    "                    return max(ans, nums[i] + score(j))\n",
    "                ans = max(ans, nums[i] + score(j) - sub(i, j))\n",
    "            return ans\n",
    "        return score(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        @lru_cache(maxsize=n//2)\n",
    "        def dp(i, isO):\n",
    "            curIsO = nums[i] % 2 == 0\n",
    "            if i == 0:\n",
    "                return nums[i] + (0 if curIsO == isO else -x)\n",
    "\n",
    "            return max(\n",
    "                dp(i - 1, isO),\n",
    "                dp(i - 1, curIsO) + nums[i] + (0 if curIsO == isO else -x)\n",
    "            )\n",
    "\n",
    "        return max(dp(len(nums) - 1, False), dp(len(nums) - 1, True))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def f(i):\n",
    "            # 奇, 偶\n",
    "            if i == 0 and nums[0] % 2: # 为奇数\n",
    "                return nums[0], -inf\n",
    "            if i == 0 and nums[0] % 2 == 0: # 为偶数\n",
    "                return -inf, nums[0]\n",
    "            j, o = f(i - 1)\n",
    "            if nums[i] % 2: # 为奇数\n",
    "                return max(j + nums[i], o + nums[i] - x), o\n",
    "            else:\n",
    "                return j, max(o + nums[i], j + nums[i] - x)\n",
    "        return max(f(n - 1))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        # if nums[0]%2 == 0:\n",
    "        #     hq2 = [nums[0],nums[0]]\n",
    "        #     hq1= [0,0]\n",
    "        # else:\n",
    "        #     hq1 = [nums[0],nums[0]]\n",
    "        #     hq2 = [0,0]\n",
    "        # ans = nums[0]\n",
    "        # for i in range(1,n):\n",
    "        #     if nums[i]%2 == 0:\n",
    "        #         tmp1 = h2[1] + nums[i]\n",
    "        #         h2 = [nums[i],tmp1]\n",
    "        #     if hq1[1]+nums[]\n",
    "        \n",
    "        ans = nums[0]\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i,flag):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            res = 0\n",
    "            j = i\n",
    "            while j<n:\n",
    "                if nums[j]%2 == flag:\n",
    "                    res += nums[j]\n",
    "                    j += 1\n",
    "                else:\n",
    "                    break\n",
    "            if j==n:\n",
    "                return res\n",
    "            else:\n",
    "                ans1 = dfs(j+1,nums[j]%2)+nums[j]-x\n",
    "                ans2 = dfs(j+1,flag)\n",
    "                # print()\n",
    "                return res+max(ans1,ans2)\n",
    "        ans = dfs(0,nums[0]%2)\n",
    "        return ans\n",
    "                    \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        cache = dict()\n",
    "        def f(i, even):\n",
    "            if (i,even) in cache:\n",
    "                return cache[(i,even)]\n",
    "            if i == len(nums):\n",
    "                return 0\n",
    "            if i == 0: \n",
    "                return nums[i] + f(i+1, nums[i]%2==0)\n",
    "            else:\n",
    "                ans = f(i+1, even)\n",
    "                if (nums[i]%2 == 0) == even:\n",
    "                    ans = max(ans, nums[i] + f(i+1, even))\n",
    "                else:\n",
    "                    ans = max(ans, nums[i] + f(i+1, not even) - x)\n",
    "                cache[(i,even)] = ans\n",
    "                return ans\n",
    "        return f(0, True)\n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i : int, s):\n",
    "            if i == n:\n",
    "                return 0     \n",
    "                   \n",
    "            if nums[i] & 1 != s:\n",
    "                return dfs(i + 1 , s)\n",
    "            \n",
    "            res = nums[i]\n",
    "            if i + 1 < n:\n",
    "                if nums[i + 1] & 1 == s:\n",
    "                    res += dfs(i + 1 , s)\n",
    "                else:\n",
    "                    res += max(dfs(i + 1, s ^ 1) - x, dfs(i + 1 , s))\n",
    "                            \n",
    "            return res\n",
    "        \n",
    "        return dfs(0 , nums[0] & 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i, f):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            \n",
    "            t = 0 if nums[i] % 2 == f else x\n",
    "            \n",
    "            p1 = dfs(i+1, f)\n",
    "            p2 = dfs(i+1, nums[i] % 2) + nums[i] - t\n",
    "            \n",
    "                \n",
    "            return max(p1, p2)\n",
    "\n",
    "        return dfs(0, nums[0] % 2) \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def f(i: int, j: int):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            v = nums[i]\n",
    "            # 选\n",
    "            res = f(i + 1, v % 2) + v\n",
    "            if j != v % 2: res -= x\n",
    "            # 不选\n",
    "            return max(res, f(i + 1, j))\n",
    "        return f(1, nums[0] % 2) + nums[0]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
